---
title: "互质 欧拉函数"
created: 2025-11-28
tags:
  - 算法
---

# 互质 欧拉函数

算法基础课 第四章 数学知识(二) 0~46min

![[image-088125c2.png]]

```cpp
int phi(int x)

{

    int res = x;

    for (int i = 2; i <= x / i; i ++ )

        if (x % i == 0)

        {

            res = res / i * (i - 1);

            while (x % i == 0) x /= i;

        }

    if (x > 1) res = res / x * (x - 1);

    return res;

}
```

---
⬅️ [[约数问题|约数问题]] 🏠 [[00-刷题理模型]] ➡️ [[x的因子链|x的因子链]]